package algorithm;

public class leetcode_0738 {
    public int monotoneIncreasingDigits(int n) {
        if (n < 10) return n;
        int len = 0;
        int m = n;
        int a = 0;
        while (m != 0) {
            len++;
            a = m;
            m /= 10;
        }
        int[] list = new int[len];
        list[0] = a;
        int b = n % 10;
        int sum = a;
        for(int i=1;i<len;++i){
            list[i]=9;
        }
        for(int i=a;i>0;--i){
            list[0] = i;
            for(int l=1;l<len;++l){
                list[l]=9;
            }
            while(list[1]>=i) {
                if (sum_(list, len) <= n) return sum_(list, len);
                int k = len - 1;
                for (; k >= 2; --k) {
                    if (list[k] > list[k - 1]) {
                        list[k]--;
                        break;
                    } else list[k] = 9;
                }
                if (k == 1) list[1]--;
            }
            }
        sum=0;
        for(int i=0;i<len-1;++i){
            sum=10*sum+9;
        }
        return sum;
    }
    public int sum_(int[] list,int len){
        int sum=0;
        for(int i=0;i<len;++i){
            sum=sum*10+list[i];
        }
        return sum;
    }
}
